package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/binary-tree-preorder-traversal/
 * <p>
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 *
 * @author hanjuntao
 * @date 2025/8/27 0027
 */
public class L_144_二叉树前序遍历 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        //       1
        //      2  3
        //    4   5

        System.out.println(preorderTraversal3(root));  // [1, 2, 4, 5, 3]
    }

    /**
     * 递归
     *
     * 先遍历根节点，再遍历左子树，最后遍历右子树
     *
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<Integer> result = new ArrayList<>();

        pre(root, result);
        return result;
    }

    private static void pre(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        result.add(root.val);
        pre(root.left, result);
        pre(root.right, result);
    }

    /**
     * 迭代
     *
     * 用迭代版。需要考虑：
     * 1. 由于是先访问根节点，再访问左子树，然后访问右子树，即对于任意一个子树
     * 2. 可以先打印根节点，再打印左子树，最后打印右子树
     *
     *
     *
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();

        List<Integer> result = new ArrayList<>();

        while (root != null || !stack.isEmpty()) {
            // 遍历左子树，直到为空，将根节点入栈
            while (root != null) {
                // 先打印根节点
                result.add(root.val);
                // 根节点入栈
                stack.push(root);
                root = root.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            // 栈不为空，说明有右子树，将栈顶元素出栈，并遍历右子树
            root = stack.pop();
            root = root.right;
        }

        return result;
    }

    /**
     * 迭代
     *
     * 用迭代版。需要考虑：
     * 1. 由于是先访问根节点，再访问左子树，然后访问右子树，即对于任意一个子树
     * 2。 由于栈后入先出，需要先将右子树入栈，再将左子树入栈
     *
     *
     *
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal3(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        Stack<TreeNode> stack = new Stack<>();

        List<Integer> result = new ArrayList<>();
        // 根节点入栈
        stack.push(root);

        while (!stack.isEmpty()) {
            // 先打印根节点
            TreeNode pop = stack.pop();
            result.add(pop.val);

            // 由于栈后入先出，需要先将右子树入栈，再将左子树入栈
            if (pop.right != null) {
                stack.push(pop.right);
            }

            if (pop.left != null) {
                stack.push(pop.left);
            }
        }

        return result;
    }
}
